In these systems, the 2D image plane is subdivided into preferably rectangular regions of pixels and, for each such region, a list of the objects that are ‘of interest’ to that region is compiled. These regions will be referred to as tiles. When the list for a particular tile contains all such objects, the tile can be rendered entirely. An alternative scheme, (as described in our patent application PCT/GB01/02536), allows for partial rendering whereby the list may simply contain a subset of the required objects.
It is important to have cost-effective means of determining which primitives, typically triangles and line segments, should be placed in which tiles. An example is given in FIG. 1. This shows the virtual image plane (e.g. framebuffer) ‘1’, consisting of a collection of pixels, ‘2’. These pixels are grouped by tiles, ‘3’. An example primitive ‘4’, a triangle, is shown. This would then need to be placed or referenced by at least the lists for the shaded tiles, 5. Note that it is permissible to include the primitive in additional tile lists, e.g. such as for tile ‘6’, but it would be incorrect to leave it out any of the shaded tiles.
The process of determining which primitives belong in which tiles is called ‘binning’ or ‘tiling’.
Modern 3D computer games tend to have very high polygon counts and thus a high number of primitives. During the generation of the scene, many of the primitives become too small to be sampled and thus do not affect the image. This happens as the objects which they are used to represent recede into the distance. Storing these very small primitives in tile lists is an unnecessary use of time, memory, and processing effort. In FIG. 7, a simple example of a small triangle primitive, ‘53’, is shown against a grid of image pixels, ‘50’. Typically, pixels, for example ‘51’, are sampled at one point, say the top left corner, ‘52’. The triangle, ‘53’ fails to cross any of the sample locations and so will not affect the image. In this particular example, this fact can be trivially determined by considering the primitive's bounding box, ‘54’. Because this does not contain any ‘integer’ sampling locations, the primitive is redundant.
In FIGS. 8 and 9, other small triangles that miss all the sampling points are shown. In these cases, however, a bounding box rejection test will fail to cull these primitives. One naïve cost-saving approach might be to compute the area of the primitive and, if it is small, reject the surface. Unfortunately, this does not always work as an object may have been modelled by, say, by tessellation to small triangles—rejecting all small triangles could easily make the entire object disappear!
In 3D computer graphics, it is common for triangular/convex polygonal primitives to be defined with an associated ‘winding order’ which is typically one of {Both, Clockwise, Anticlockwise}. The winding order is used as a performance optimization to eliminate some primitives prior to rendering. This optimization functions such that if, after projection, the primitive has an order of vertices that does not match its specified winding order, that primitive can be ignored.
In the IEEE 754 standard, floating point numbers are represented using a sign bit value, sign, an exponent value, ex, and an ‘M’ bit mantissa value, m, which with the exception of some minor special cases which can be ignored, represents a value equal to
                    (                  -          1                )            sign        ⁢                  .2        ex            .              (                  1          +                      m                          2              M                                      )              ,where 0≦m<2M. For 32-bit IEEE floating point numbers, M is 23, but reduced precision maths could use fewer bits. If a system were converting a normalized IEEE float, x, to a system that uses M bits for the mantissa, then it can be shown that the error in the approximated x value,
      x    M    ,obeys the inequality . . .
                              err          ⁡                      (                          x              M                        )                          ≤                              1                          2                              M                +                1                                              ⁢                                  x                                                          eqn        ⁢                                  ⁢        1            
Similar expressions for addition and multiplication operations can be derived:
                              err          ⁡                      (                                          x                M                            +                              y                M                                      )                          ≤                              err            ⁡                          (                              x                M                            )                                +                      err            ⁡                          (                              y                M                            )                                                          eqn        ⁢                                  ⁢        2                                          err          ⁡                      (                                          x                M                            ·                              y                M                                      )                          ≤                                            err              ⁡                              (                                  x                  M                                )                                      ⁢                                        y                                              +                                    err              ⁡                              (                                  y                  M                                )                                      ⁢                                        x                                              +                                    err              ⁡                              (                                  x                  M                                )                                      ⁢                          err              ⁡                              (                                  y                  M                                )                                                                        eqn        ⁢                                  ⁢        3            
In GB2343603, a method of determining which primitives (i.e. the basic rendering components used to represent objects) are in a particular tile is presented. For each primitive (in particular, a triangle) it first determines a bounding box of candidate tiles and then attempts to eliminate a candidate tile by testing each of the edge equations against certain corner points of that tile. For each edge, only one corner of each tile needs to be tested. If the candidate is not eliminated, then the primitive is added to the tile's list.
There are several inconvenient aspects with the approach described in that patent:
(1) The precision of the mathematics used to perform the rejection calculations must be at least as accurate as, or at least give identical results to, that used by the rendering system when that decides which pixels a primitive covers.
An example of a potential problem is shown in FIG. 2. A 2×2 subset of the image's tiles, ‘7’, consisting of a number of pixels, 8, is shown along with a boundary edge of a primitive, ‘9’. Those pixels, shown in grey, represent the pixels that may be deemed to be ‘inside’ the primitive by the renderer. Obviously, any tile that contains such a pixel, even if there is only one such pixel, e.g. ‘10’, should also have the primitive included in its list.
This may seem like a triviality, but in practice it may be more complicated. For example, floating point arithmetic may be used to perform the various inside/outside tests, and when rendering a particular tile, the coordinate system may be re-aligned so that rather than using a pixel origin that is at the top left of the image, the rendering may use a local origin, say, at the top left of the tile. Doing this reduces the cost of the hardware needed when rendering inside the tile, however, it would make it very difficult and/or more expensive to have a ‘global test’ with exactly the same accuracy that can be used for the ‘tiling’ operation. If there is any deviation in accuracy, then there is a chance that tile ‘11’ might be deemed to not include the primitive and hence cause pixel ‘10’ to be rendered incorrectly.
Even if the mathematics provides exactly the same results as that used inside the renderer, a hardware solution would require a significant amount of silicon.
An alternative could be to use fixed-point mathematics, rather than floating-point, but this incurs the problem that arbitrary polygons would have to be ‘clipped’ to the valid supported mathematical range. Clipping is an expensive operation which is preferable to avoid.
(2) The ‘test corner’ of the tile varies depending on the parameters of the particular edge's line/plane equation. This is an inconvenience, as it requires decisions on a tile-by-tile/edge-by-edge basis.
(3) The system only supported triangles and it is useful to also apply the ‘tiling’ process to other primitive types such as ‘thick lines’ constructed from parallelograms. Of course, it is trivial to either convert a parallelogram to a pair of triangles, or even extend the method to support any convex polygon, but for the case of lines a more efficient approach is desirable.
(4) The system does not attempt to address cases where ‘tiny’ primitives, e.g. those that are around the size of a pixel, are supplied to the tiling engine but don't actually get rendered. Many such primitives, such as those illustrated in FIGS. 6 thru 8 simply will not affect the outcome of the final image because they fall between the ‘sampling points’ used in the renderer. Adding these to the tile list is thus wasted effort.